package org.leetcode.middle.leetcode347;

import java.util.*;

public class Solution
{

    public static void main(String[] args) {
//        Map<Integer,Integer> map = new HashMap<>();
//
//        map.put(2,3);
//        map.put(5,3);
//        map.put(6,3);
//
//        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
//
//        System.out.println(entries.size());
        int [] nums = {1,1,1,2,2,3};

        for (int num : topKFrequent2(nums, 2)) {
            System.out.println(num);
        }


    }


    public static int[] topKFrequent2(int[] nums, int k) {
        int [] res = new int[k];

        HashMap<Integer,Integer> hashMap = new HashMap<>();

        for (int num:nums) {
            if (hashMap.containsKey(num)){
                hashMap.put(num,hashMap.get(num)+1);
            }else {
                hashMap.put(num,1);
            }
        }

        PriorityQueue<int []> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(arr -> arr[1]));

        for (Map.Entry<Integer,Integer> item:hashMap.entrySet()) {
            if (priorityQueue.size()>=k){
                if (item.getValue()>priorityQueue.peek()[1]){
                    priorityQueue.poll();
                    int [] temp ={item.getKey(), item.getValue()};
                    priorityQueue.add(temp);
                }
            }else {
                int [] temp ={item.getKey(), item.getValue()};
                priorityQueue.add(temp);
            }
        }

        for (int i = 0; i < k; i++) {
            res[i]=priorityQueue.poll()[0];
        }

        return res;
    }
    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序
            if (pq.size() < k) { //小顶堆元素个数小于k个时直接加
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }


}
